home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000004_icon-group-sender _Wed Dec 7 21:38:35 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  1KB
  1. Received: by cheltenham.cs.arizona.edu; Wed, 7 Dec 1994 23:00:02 MST
  2. To: icon-group-l@cs.arizona.edu
  3. Date: 7 Dec 1994 21:38:35 -0700
  4. From: dave@cs.arizona.edu (Dave Schaumann)
  5. Message-Id: <3c62kb$pnu@caslon.CS.Arizona.EDU>
  6. Organization: University of Arizona CS Department, Tucson AZ
  7. Sender: icon-group-request@cs.arizona.edu
  8. References: <1994Dec7.221649.10939@cs.sfu.ca>
  9. Subject: Re: [Q] Algorithm for Regexp Subsumption
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12.  
  13. In article <1994Dec7.221649.10939@cs.sfu.ca>,
  14. Martin Vorbeck <vorbeck@cs.sfu.ca> wrote:
  15.  
  16. }  are there any algorithms out there for checking whether a regular
  17. }expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a
  18. }"brute-force" solution along these lines:
  19. }
  20. }1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2).
  21. }2. Compute A3 = A1 intersected with the complement of A2.
  22. }3. Test L(A3) = empty  ==>  E2 subsumes E1.
  23. }
  24. }But I wonder if this couldn't be done directly on the regular
  25. }expressions E1 and E2?
  26.  
  27. Another possibility would be to compute the minimized DFAs, then
  28. compute the minimized DFA of the union.  If it's the same as either
  29. of the originals, you've got a match.
  30.  
  31. Hard to say which method would be quicker.  Since they're essentially
  32. duals of each other, I wouldn't be surprised if it was a wash.
  33.  
  34. -Dave